package m202403.d12;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/3/12 15:19
 */
//70. 爬楼梯
public class Q70 {

    static int[] cache = new int[45];

    static {
        cache[0] = 1;
        cache[1] = 2;
    }

    public int climbStairs(int n) {
        int result = cache[n - 1];
        if (result > 0) {
            return result;
        } else {
            result = climbStairs(n - 1) + climbStairs(n - 2);
            cache[n - 1] = result;
        }
        return result;
    }
}
